package violencerecursion;

import java.util.LinkedList;
import java.util.List;

/**
 * @author tongchen
 * @create 2023-03-15 23:12
 */
public class FullArrangementBranchGauge {
    public static void main(String[] args) {
        String s="aaa";
        System.out.println(fullArrangement(s));
    }
    public static List<String> fullArrangement(String s){
        //创建新list
        LinkedList<String> list = new LinkedList<>();
        //将数组转化为字符串
        char[] chars = s.toCharArray();
        //从开头的位置不断向后递归
        process(chars,0,list);
        return list;
    }

    private static void process(char[] chars, int i, LinkedList<String> list) {
        //设置终止条件
        if(i== chars.length){
            //将排列的结果加入字符数组
            list.add(String.valueOf(chars));
        }
        //创建一个负责检查当前位置是否重复的哈希表，如果当前位置重复，直接不走当前路径
        boolean [] checks=new boolean[26];
        //从当前位置开始与往后的字符交换生成结果
        for (int j = i; j <chars.length ; j++) {
            if(!checks[chars[j]-'a']){
                checks[chars[j]-'a']=true;
                swap(chars, i,j );
                //进入下一个位置
                process(chars, i+1, list);
                //恢复
                swap(chars,j,i);
            }
            //直接跳过
        }
    }
    private static void swap(char[] chars, int i, int j) {
        char temp=chars[i];
        chars[i]=chars[j];
        chars[j]=temp;
    }
}
